package com.c2b.algorithm.leetcode.base;

/**
 * <a href="https://leetcode.cn/problems/binary-tree-pruning/">二叉树剪枝(Binary Tree Pruning)</a>
 * <p>给你二叉树的根结点 root ，此外树的每个结点的值要么是 0 ，要么是 1 。</p>
 * <p>返回移除了所有不包含 1 的子树的原二叉树。</p>
 * <p>节点 node 的子树为 node 本身加上所有 node 的后代。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1：
 *      输入：root = [1,null,0,0,1]
 *              1                       1
 *               \                       \
 *                0         ==>           0
 *               / \                       \
 *              <a color="red">0</a>   1                       1
 *
 *      输出：[1,null,0,null,1]
 *      解释：
 *          只有红色节点满足条件“所有不包含 1 的子树”。 右图为返回的答案。
 *
 * 示例 2：
 *      输入：root = [1,0,1,0,0,0,1]
 *               1                      1
 *             /   \                     \
 *            <a color="red">0</a>     1       ==>           1
 *           / \   / \                     \
 *          <a color="red">0</a>   <a color="red">0</a> <a color="red">0</a>   1                     1
 *      输出：[1,null,1,null,1]
 *
 * 示例 3：
 *      输入：root = [1,1,0,1,1,0,1,0]
 *                   1                      1
 *                 /   \                 /    \
 *                1     0       ==>     1      0
 *               / \   / \             / \      \
 *              1   1 <a color="red">0</a>   1           1   1      1
 *             /
 *            <a color="red">0</a>
 *      输出：[1,1,0,1,1,null,1]
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>树中节点的数目在范围 [1, 200] 内</li>
 *     <li>Node.val 为 0 或 1</li>
 * </ul>
 * </p>
 * @author c2b
 * @since 2023/5/25 11:09
 */
public class LC0814BinaryTreePruning_M {

    static class Solution {
        public TreeNode pruneTree(TreeNode root) {
            return pruneTreeByRecursion(root);
        }

        public TreeNode pruneTreeByRecursion(TreeNode root) {
            if (root == null) {
                return null;
            }
            root.left = pruneTreeByRecursion(root.left);
            root.right = pruneTreeByRecursion(root.right);
            if (root.val == 0 && root.left == null && root.right == null) {
                return null;
            }
            return root;
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(1);
        root.left.left = new TreeNode(1);
        root.left.right = new TreeNode(1);
        root.left.left.left = new TreeNode(0);
        root.right = new TreeNode(0);
        root.right.left = new TreeNode(0);
        root.right.right = new TreeNode(1);
        Solution solution = new Solution();
        TreeNode.printTree(solution.pruneTree(root));
    }
}
